package com.kevin.Code.OfferReviewVersion2;

import java.util.Arrays;

/**
 * @author Vinlee Xiao
 * @Classname IsGraphBipartite
 * @Description 剑指 Offer II 106. 二分图 同Leetcode 785. 判断二分图 中等难度
 * @Date 2022/1/11 11:06
 * @Version 1.0
 */
public class IsGraphBipartite {

    /**
     * 思路:遍历邻接节点
     *
     * @param graph
     * @return
     */
    public boolean isBipartite(int[][] graph) {

        int[] colors = new int[graph.length];
        //对colors数组置为零
        Arrays.fill(colors, -1);

        for (int i = 0; i < graph.length; i++) {
            if (colors[i] == -1) {
                if (!dfs(graph, colors, i, 0)) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 主要考察对于图邻接矩阵的掌握情况
     * 深度优先遍历的思路
     *
     * @param graph
     * @param colors
     * @param color
     */
    public boolean dfs(int[][] graph, int[] colors, int index, int color) {
        //colors[index]>=说明已经着色过
        if (colors[index] >= 0) {
            //着色相同说明是二分图 否则不是二分图
            return colors[index] == color;
        }
        colors[index] = color;

        //对节点graph的相邻节点进行着色
        for (int i : graph[index]) {
            //如果相邻节点有不符合二分图的直接返回false
            if (!dfs(graph, colors, i, 1 - color)) {
                return false;
            }
        }
        return true;
    }
}
